<!DOCTYPE html>
<html lang="en">
  <head>
    <meta charset="UTF-8" />
    <meta name="viewport" content="width=device-width, initial-scale=1.0" />
    <meta http-equiv="X-UA-Compatible" content="ie=edge" />
    <title>快速排序</title>
  </head>
  <body>
    <div>
      快速排序，又称划分交换排序。以分治法为策略实现的快速排序算法。<br />
      本文主要要谈的是利用javascript实现in-place思想的快速排序<br />
      分治法：<br />
      在计算机科学中，分治法是建基于多项分支递归的一种很重要的算法范式。字面上的解释是“分而治之”，就是把一个复杂的问题分成两个或更多的相同或相似的子问题，<br />
      直到最后子问题可以简单的直接求解，原问题的解即子问题的解的合并。（摘自维基百科）<br />
      快速排序的思想<br />
      数组中指定一个元素作为标尺，比它大的放到该元素后面，比它小的放到该元素前面，如此重复直至全部正序排列。<br />
      快速排序分三步：<br />
      选基准：在数据结构中选择一个元素作为基准(pivot)<br />
      划分区：参照基准元素值的大小，划分无序区，所有小于基准元素的数据放入一个区间，所有大于基准元素的数据放入另一区间，分区操作结束后，基准元素所处的位置就是最终排序后它应该所处的位置<br />
      递归：对初次划分出来的两个无序区间，递归调用第 1步和第
      2步的算法，直到所有无序区间都只剩下一个元素为止。<br />
    </div>
    <img src="../../../image/排序/快速排序.png" alt="" srcset="">
    <script>
      var arr = [31, 12, 24, 5, 6, 84, 3, 5, 323, 79, 45, 2, 21, 78, 31];

      // 普遍实现快速排序的方法
      function quickSort(arr) {
        console.time("快速排序");
        if (arr.length <= 1) {
          return arr;
        }
        var pivotIndex = Math.floor(arr.length / 2); // 指定分区基点
        var pivot = arr.splice(pivotIndex, 1)[0]; // 这里需要改变原数组提出基元素  作为递归的关闭条件
        var left = [];
        let right = [];
        for (var i = 0; i < arr.length; i++) {   
          if (arr[i] < pivot) {
            left.push(arr[i]);
          } else {
            right.push(arr[i]);
          }
        }
        console.timeEnd("快速排序");
        return quickSort(left).concat([pivot], quickSort(right)); // 合并每次分完的数组
      }
      console.log(quickSort(arr)); // [2, 3, 5, 5, 6, 12, 21, 24, 31, 31, 45, 78, 79, 84, 323]
    </script>
  </body>
</html>
